{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. dp数组以及下标的含义  \n",
    "2. 递推公式  \n",
    "3. dp数组如何初始化  \n",
    "4. 遍历顺序  \n",
    "5. 打印dp数组  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "动态规划题目特点  \n",
    "1. 计数  \n",
    "有多少种方法走到右下角  \n",
    "有多少种方法选出k个数使得和是sum  \n",
    "2. 求最大最小值  \n",
    "从左上角走到右下角路径的最大数字和  \n",
    "最长上升子序列长度  \n",
    "3. 求存在性  \n",
    "取石子游戏,先手是否必胜  \n",
    "能不能选出k个数使得和是sum  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "动态规划组成部分  \n",
    "1. 确定状态  \n",
    "最后一步(最优策略中使用的最后一枚硬币ak)  \n",
    "化成子问题(最少的硬币拼出更少的面值27-ak)  \n",
    "2. 转移方程  \n",
    "f[x]=min{f[x-2]+1, f[x-5]+1, f[x-7]+1}  \n",
    "3. 初始条件和边界情况  \n",
    "f[0]=0,如果不能拼出Y,则f[Y]=∞  \n",
    "4. 计算顺序  \n",
    "f[0],f[1],f[2],..."
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
